• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The present invention describes mechanisms that sequentially explore a network of transparent bridges to establish multiple bidirectional paths disjoint in links or in nodes and links, between pairs of bridges bordering the network, as well as a network bridge that implements said mechanisms. The origin boundary bridge sends multicast road-laying packages to the destination bridge that propagate to the destination bridge, which confirms each disjoint road establishment. The roads are automatically deleted when a certain time passes without confirmation, without being used or when sending the frontier bridge an explicit erasure packet of a road or all roads. The number of created paths is parameterizable and both ends communicate the number of output links to know the maximum number of feasible paths. These multiple disjoint paths created by the border bridges can be used by an entity or protocol that requires multiple disjoint roads for reasons of load sharing, reliability or others. (Machine-translation by Google Translate, not legally binding)
    公开号:ES2638292A1
    申请号:ES201600207
    申请日:2016-03-18
    公开日:2017-10-19
    发明作者:Guillermo IBÁÑEZ FERNÁNDEZ；Joaquín ÁLVAREZ HORCAJO；Juan Antonio Carral Pelayo；Isaías MARTINEZ YELMO；Diego LÓPEZ PAJARES
    申请人:Universidad de Alcala de Henares UAH；
    IPC主号:
    专利说明:

    DESCRIPTION

    Procedure for establishing and deleting multiple disjoint roads, frame forwarding and network bridge.
     5
    Technical sector

    The present invention falls within the field of communications and electronic devices and / or computer applications that establish communications between transparent network bridges. 10

    State of the art

    The path establishment protocols known as Fast-Path and ARP-Path [G. are known. Ibáñez, J. A Carral, A Garcia-Martinez, J. M. Arco, D. Rivera, and A Azcorra, "Fast 15 Path Ethernet Switching: On-demand, Efficient Transparent Bridges for Data Center and Campus Networks". 17th IEEE Workshop on Local and Metropolitan Area Networks (LANMAN). New Jersey, USA, May 2010.] [G. Ibáñez, J.A. Carral, J.M. Arco, D. Rivera, and A. Montalvo. "ARP Path: ARP-Based, Shortest Path Bridges". IEEE Communications Letters. 2011, pp. 770-772.], Which establish paths through simultaneous exploration of the entire network through a broadcast frame such as the ARP Request and perform learning on the bridges across the source MAC addresses and their association to the port through which it is first received The broadcast plot. The procedure for establishing the mentioned road operates as follows: In a network of ARP-Path bridges, two terminals A and C establish to communicate two paths from A to C and from C to A These paths are learned in the bridges of the network by 25 the diffusion by all the links of a broadcast frame as ARP Request or by means of its response, a unicast frame like ARP Reply. The bridges associate to the MAC address of the frame the port through which the frame is first received and block this association preventing its modification for a sufficient time so that copies received in other ports of each bridge are discarded because they are not associated its source MAC address 30 to the port through which they are received. These paths can also be established in the manner known as Flow-Path by sending an ARP Request (of which the origin MAC and the origin and destination IP are registered in the origin border bridge) and an answer ARP Reply that confirms the bidirectional and symmetric path associated with the source and destination MAC addresses. [Elisa Rojas, Guillermo Ibáñez, Diego Rivera, Juan A Carral, "Flow-Path: An AllPath flow-based protocol", 35 Proceedings of the 2012 IEEE 37th Conference on Local Computer Networks (October 2012) pp. 244-247].

    Also known are the protocols that associate under certain conditions the MAC address origin of unicast frames to an input port and verify when they receive a unicast or multicast frame whether or not the port is associated with said frame [Minkenberg et al. US2011 / 0032825A1. Multipath discovery in switched Ethernet networks. Publication date, February 10, 2011.] [Tanaka et al. First arrival port learning method, relay apparatus, and computer product. US 7760667 82] [Mack-Crane et al. Media access control bridging in a mesh network. US 2010/0272108 A1]. Four. Five

    Road establishment protocols for transport connections [G. Ibáñez, Method for establishing and clearing paths and forwarding trames for transport connections, and network bridge WO 2015086877 A1] allow to establish paths in the network by direct exploration of the network with multicast frames replicated in the network, but more specifically, associating each path with a data flow, taking into account additional fields transported in the frames such as the transport ports (TCP, UDP or others) used in the connection between the two terminals to identify each data flow and
    using the SYN TCP indicator in the received frame to begin the search for a new path for the new data transport connection that said SYN packet establishes.

    It is also common in the state of the art to distinguish the frames that a protocol must process through the Ethertype field of the Ethernet 5 frame http://www.iana.org/assignments/ieee-802-numbers/ieee-802-numbers. xhtml]. For example, the ARP protocol is assigned the Ethertype 806h and treats the ARP control packets because layer two associates that type with the protocol, the data packets will carry the 800h ethertype corresponding to the IP packets, therefore being processed by the protocol IP. 10
    But none of the aforementioned protocols guarantees that the various paths created are disjoint, that is, that no pathway shares a link with one another (disjoint path in links) or does not share or link or any bridge (path disjoint in bridges and therefore in links).
     fifteen
    Methods of establishing multiple paths known as Equal Cost Multiple Path (ECMP) [RFC2992, C. Hopps, IETF 2000] are also known, in which multiple paths are obtained by calculation on a graph representing the network instead of by physical network scanning through frames.
     twenty
    In wired networks the best known protocol that uses Equal Cost Multiple Path is Shortest Path Bridging [1]. Shortest Path Bridging requires full knowledge of the network topology and perform extremely complex calculations on the network graph (multiple symmetric minimum paths between nodes eligible by priorities sorted according to the list of bridge identities, computational complexity Θ (N * * 3)) to obtain multiple routes 25 disjoint in the network graph.

    For Ad Hoc mobile networks there are many protocols aimed at wireless and mobile networks, derived from the Ad Hoc Distance Vector (AODV) [3] or Dynamic Source Routing (DSR) [2] protocol, based on explicit route search protocol, with responses that 30 contain explicit routes. Split multipath (SMR) [4) DSR extension; Ad hoc On-demand Multi-path Distance Vector (AOMDV) routing protocol (disjoint routes in links) [5], AODV-Multi-path protocol [6] (disjoint routes in nodes); Geographic Multi-path Routing Protocol (GMRP) [7] and Energy-aware Multi-path Routing Protocol (EMRP) [8]. The AODV and DSR derived protocols require comparison of the many duplicate packets with routes that arrive at the bridges to update the received route and retransmit the shortest received.

    Description of the invention

    The present invention describes mechanisms that allow establishing (searching for a path in the network and confirming it), using and deleting multiple paths, partially or totally disjoint (disjoint only in links or also disjoint in nodes (i.e. bridges) between two bridges border of a network that are located at any point of the network, as well as a network bridge that implements such mechanisms.It is understood by partially disjointed road that which, having some link without sharing with any of the other roads, crosses some link 45 assigned to another path established between the same border and destination bridges.The multiplicity of the paths created is parameterizable.

    These roads between bridges can be assigned to traffic flows between terminals in various ways in order to distribute the traffic between the available roads 50

    The invention includes an iterative method of searching and confirming disjoint paths between the bridges of the network, a method of forwarding user frames through said paths and a method for deleting them. These procedures will apply.
    by the Multiple_Disjoint_Path bridges that have this functionality activated, configurable according to the network requirements. These multiple disjoint roads created by border bridges can be used by an entity or protocol that requires multiple disjoint paths for reasons of load sharing, reliability or others. This will require appropriate interfaces so that other devices or programs can use this multi-path establishment service.

    Successive establishment of multiple disjoint paths

    Prior to the establishment of roads, each bridge needs to know the MAC address of the 10 other border bridges and the terminals connected to each of them. The bridge creates and maintains a list of the terminals that are connected to it.

    The bridges use a procedure to announce to the other bridges their MAC address and that of the terminals connected to them, as follows: when a bridge is initialized, and then periodically, it proceeds to establish a generic path of all the bridges to issuing a SetTree multicast packet with its MAC address as the source address and with the destination address the multicast address associated with the specific Multiple_Disjoint_Path protocol assigned to Multiple_Disjoint_Path, the frame containing the list of terminals connected to the bridge. twenty

    Each bridge, upon receiving the Set tree frame, associates the port through which it is first received to the bridge's home address.

    Search and confirmation of multiple disjoint paths 25

    The multi-path search uses the procedure known as FastPath and ARP-Path to select the fastest path in the network. An origin border bridge A establishes up to a variable number N of multiple disjoint or partially disjoint roads (if the roads share a link) with a destination bridge H as follows:

    In a bridge network, the border bridge (also known as the access bridge) begins the establishment of multiple disjoint paths by sending to each of the other bridges a multicast path search frame containing the destination bridge, number Sequence of road identifier between the pair of bridges and an indicator of 35 type of disjoint road that can initially go empty. The packet is forwarded by all the bridges, the way being learned temporarily (by association of the originating MAC address to the first port that receives the frame and the transitory blocking of that association to new associations to other ports) towards the origin bridge in the ports where the frame is received first and discarding duplicate packets received by other ports later. 40 are associated in a table, for forwarding purposes, the source and destination MAC addresses, as well as the multi-path identifier sequence number #i, to the identity of the bridge port that first received the frame, to an expiration indicator and upon arrival of the plot; and it is forwarded on broadcast by all ports except the receiving port.
     Four. Five
    Each bridge that receives the path search frame #i (the sequence number of the first path) associates the bridge address (MAC address origin of the frame sent) to the port where the frame is first received and forwards it through all ports except for the arrival one, the association of the originating address to the port lasts long enough to prevent the formation of loops so that in each bridge only the frame received first will be the only one retransmitted, because the duplicated frames subsequently received by other ports They are discarded when they are received by a port other than that associated with the MAC address of the frame.

    Finally, only one path search frame #i (the sequence number of the first path) will be accepted (those received by other ports will be discarded by the bridge itself) on the border bridge H, which records the port where it receives the frame and associate it with the directions of the two border bridges A and H as path #i (the sequence number of the first path) bidirectional to use. To confirm the establishment of the first bidirectional path 5 between A and H, the bridge H responds by sending a unicast path confirmation path #i (the sequence number of the first path) through the port through which it was received, with the address address the address of bridge H, destination address the address of bridge A and protocol identifier (Ethertype) the specific assigned to Multiple_Disjoint_Path. This frame travels in the opposite direction the path between A and H so that in each bridge of the network 10 that receives this frame, the frame is forwarded by the port associated to the address of A and the path is noted in its forwarding table bidirectional #i (the sequence number of the first path) between bridges A and H and the two ports associated with said bidirectional path, thus leaving the bidirectional path #i (the sequence number of the first path) between established A and H, starting a validity timer of the path #i (the sequence number of the first path) and a timer for the establishment of path # i + 1 (the sequence number of the second path).

    Bridge A, once established the disjoint path #i (the sequence number of the first path) proceeds to establish a new disjoint path # i + 1 (the sequence number of the second path) by sending a path search frame with sequence number of path identifier # i + 1 (the sequence number of the second path). If the desired path is disjoint in links, bridge A sends the request indicating the type of disjoint path in links through all ports except for the port associated with the path #i (the sequence number of the first path) to prevent the new path # i + 1 (sequence number 25 of the second path) use links already assigned to path #i. Each bridge that receives the path search path # i + 1 (the sequence number of the second path) learns the originating address of bridge A and the originating MAC address, associates it with the port through which it is received first, and forwards it by all other ports except for the ports associated with the path #i (the sequence number of the first path) (ports associated with the MAC address pair 30 of the AB bridges and the path identifier sequence number #i). Finally, only one or no road search frame # i + 1 (the sequence number of the second road) will be accepted (those received by other ports will be discarded by the bridge itself) on the border bridge H, which will record the port where it receives the frame and associates it with the addresses of the two border bridges A and H as path # i + 1 (the sequence number of the second path) bidirectional to use. To confirm the establishment of the first bidirectional path between A and H on all the bridges crossed, bridge H responds by sending a path confirmation path Path Confirm # i + 1 (the sequence number of the second path) by the port where it was received, with the source address the address of bridge H and destination address the address of bridge A. 40 This frame travels in the opposite direction the path between A and H so that in each bridge of the network that receives this frame, the frame is forwarded by the port associated to the address of A and the bidirectional path # i + 1 (the sequence number of the second path) between bridges A and H [and terminals a and b] and is recorded in its forwarding table the two ports associated with said bidirectional path thus leaving bidirectional path # i + 1 (the sequence number of the second path) between A and H established, starting a validity timer of the path.

    If the desired path is disjoint in nodes, bridge A sends the request indicating the type of disjoint path in nodes by all ports except for the port associated with path #i (the 50 sequence number of the first path) to prevent the new path # i + 1 (the sequence number of the second path) use links already assigned to path #i. Each bridge that receives the path search path # i + 1 (the sequence number of the second path) checks if it has an assigned path with sequence identification number
    less than that of the received path search plot and if so, discards the request and does not forward it. If not, it learns the originating address of bridge A and the originating MAC address, associates it with the port through which it is first received, and forwards it through all other ports except for the ports associated with path #i (the sequence number of the first path) (ports associated with the MAC address pair of AB bridges). 5 Finally, only one or no path search frame # i + 1 (the sequence number of the second path) will be accepted (those received by other ports will be discarded by the bridge itself) on the border bridge H, which will record the port through which it receives the frame and associates it with the addresses of the two border bridges A and H as path # i + 1 (the sequence number of the second way) to be used. This process is repeated for successive paths.

    The Path Request path search package contains a field that indicates the number of links of the source bridge that bind it to other bridges and are active and another field with the number of paths confirmed by the destination bridge, the Path Confirm package also contains 15 two fields respectively with the same contents. The origin bridge decides to make new attempts to establish disjoint roads based on these fields and the number of attempts already made. Likewise, the origin bridge can start trying to establish disjoint paths in nodes, then disjoint in links and finally it can establish paths that are not necessarily disjoint if it does not reach enough to maximize the connectivity of the network topology.

    Road erase

    If the paths are not used by the frames associated with them (frames between terminals 25 and b) for a period longer than the persistence timer (cache) of the bridges, they expire automatically, deleting the ports associated with the path.

    Likewise, when an established road is interrupted, due to a link or bridge failure, the immediate erasure of the addresses learned in the port occurs, associated in table 30 of forwarding to the port connected to the failed link or bridge and as a consequence of the roads associated with these directions.

    Similar to the establishment, the paths can be explicitly erased by the end bridges by means of a Path Delete unicast packet 35 sent by the road and containing the road identifier and the pair of MAC addresses of the bridges or a multicast package that indicates deletion of all paths between the pair of origin and destination bridges.

    Frame Forwarding 40

    The frames received on a bridge can be control or user (data frames).
    If there is a multiple path associated with the frame (according to its tuple source MAC address and destination MAC), the following procedure is used to forward it. Each unicast user frame (data) received contains the destination and source terminal MAC address. The address of the destination terminal is consulted in the global bridge-bridge table and the MAC address of the border bridge to which the destination terminal is connected is obtained. For each destination bridge will be created between 1 and n disjoint roads. In both border bridges and intermediate bridges, each data frame is uniquely associated with a multiple path established between the origin and destination bridges by applying a 50 hash function to the tuple formed by the source and destination addresses of the terminals, function whose maximum result coincides with the number of disjoint paths available between the bridges, associating the result with the corresponding path, if the result is zero to the first path
    assigned, if it is 1 to the second, and so on. If the result of the hash is greater than the number of available paths, this result is divided by two and reassigned.

    Each bridge selects the hash function in a coincident way, so that it returns as many possible results as the number of paths that have been assigned between the two 5 bridges. This number is obtained by each bridge, both border and intermediate, as the difference, increased by one, between the sequence numbers of the last and the first path confirmed during the last sequence of establishment of multiple paths between both bridges.
     10
    In this way any bridge in the network knows to which flow / path a frame belongs for routing purposes. The frame is sent through the port associated with that path according to the hash obtained. In each bridge crossed, the forwarding is carried out in the same way by consulting the arrival port and the origin and destination MAC addresses, reading in the table the output port associated to the corresponding path. If there is a port associated with said path as destination, the frame is forwarded through the port associated with said connection to the destination terminal and the timer associated with the multiple path number is renewed for an additional period; if it does not exist, it is checked, in a less restrictive way, if there is any port of the associated bridge (by another protocol or procedure) only to the destination MAC address of the frame, if it exists the frame is forwarded by that port. twenty

    After a while without being used, the roads are cleared. Border bridges configured for this purpose proactively and periodically establish multiple paths between the bridges through multicast frames.
     25
    When a unicast data frame is received on a network bridge, after consulting the origin and destination bridges in the table, it is checked whether there are several multiple paths for that origin and destination address tuple in the routing table and if so, it is performed the hash function on the tuple of source MAC address and destination MAC to determine the path to be used for the forwarding of that frame. 30

    Road renovation

    When a data frame is received on a bridge, the validity timer of the path used by the frame is renewed, extending its validity for an additional interval of 35 expiration since it is received.

    Network bridge for multiple paths disjoint

    The mechanisms for establishing roads, clearing roads and forwarding frames 40 described can be implemented in a network bridge that has the corresponding tables to associate the ports to tuples formed by pairs of MAC addresses ab of the terminals and border bridges respective AH as well as the sequence number of the road identifier and the path duration timer.
     Four. Five
    Brief description of the drawings

    Figure 1 shows the flowchart of the procedure for establishing multiple paths disjoint in links.
     fifty
    Figure 2 shows the processing of the frames received on a bridge and the actions when a timer expires.

    Figure 3 shows the search for the first path (path identifier #i) disjoint in links between two bridges connected to a multiple_Disjoint_Path bridge network and the confirmation with the path confirmation path Path Confirm.

    Figure 4 shows the establishment of the disjoint path on links # i + 1 (second path) 5 between two border bridges.

    Figure 5 shows the establishment of the disjoint road in links # i + 2 (third road) between two border bridges.
     10
    Figure 6 shows the establishment of the disjoint road in links # i + 3 (fourth road) between two border bridges.

    Figure 7 shows the state of the network after establishing the roads.
     fifteen
    Figure 8 shows the deletion of a path using Path Delete # i + 2.

    Figure 9 shows the network after deletion of path # i + 2.

    Figure 10 shows the deletion of all paths between A and H by All Path Delete. twenty

    Figure 11 shows the state of the roads after the subsequent erase.

    Figure 12 shows the flow chart of the procedure for establishing multiple paths disjoint at nodes. 25

    Figure 13 shows the establishment of the disjoint path in nodes #i (the sequence number of the first path) between two border bridges.

    Figure 14 shows the establishment of the disjoint path in nodes # i + 1 (the 30 sequence number of the second path) between two border bridges.

    Figure 15 shows the establishment of the disjoint path in nodes # i + 2 between two border bridges.
     35
    Figure 16 shows the failed attempt to establish the disjoint path in nodes # i + 3 between two border bridges.

    Figure 17 shows the format of a control frame of the Multiple_Disjoint_Path protocol.
    Figure 18 shows the format of a Set Tree frame. 40

    Figure 19 shows the format of the tables of a bridge.

    Figure 20 shows the state of table 1 of bridge C and the state of tables 2 and 3 of bridge A when Path Request 1 is sent. Table 2 exists on all bridges. Four. Five

    Figure 21 shows the state of table 1 of bridge C and the state of tables 2 and 3 of bridge A when the path confirmation path Path Confirm 1 is received.

    Figure 22 shows the status of table 1 of bridge C and table 2 of bridge A when Path Request 2 is sent.

    Figure 23 shows the status of table 1 of bridge C and table 2 of bridge A when the path confirmation path Path Confirm 2 is received.
    Figure 24 shows the status of table 1 of bridge E and table 2 of bridge A before the Path Delete is sent to clear path 3.

    Figure 25 shows the status of table 1 of bridge E and table 2 of bridge A after receiving Path Delete 3. 5

    Embodiment

    An embodiment of the invention is described.
     10
    Figure 1 shows the search for the first disjoint path in links between two bridges connected to a bridge network by sending the Path Request frame and receiving a Path Confirm path confirmation frame.

    Figure 2 shows the flow chart for processing the frames received and the 15 timers that expire.

    An example network is shown in Figure 3 to describe the network scanning mechanism for searching multiple paths. Terminals a and b represent the groups of terminals connected respectively to the origin and destination border bridges A and H. Each bridge 20 periodically broadcasts (through a Set Tree broadcast frame, see figure 18) to all other bridges their identity (MAC address ) and the list of MAC addresses of the terminals directly connected to said bridge, addresses that it collects from the source MAC addresses of the ARP Request broadcast packets received and that the terminals send spontaneously. In this way all the bridges build a table of MAC addresses of terminal 25 and associated destination bridge. When a bridge receives a frame from a terminal, it consults in the list of bridge-terminals to which bridge the destination terminal is connected and associates it with one of the multiple paths previously established between the bridges by the procedure described below. This frame is routed through one of the available paths, obtaining the identifier of the path to be used by means of a hash function 30 (summary) applied to the tuple MAC address source-destination MAC address.

    The Set Tree frame is based on the combination of two mechanisms known in the state of the art: the ESADI (End Station Address Distribution Information) Protocol (https://tools.ietf.org/html/draft-ietf-trill-) packages esadi-09) that distributes the list of terminals connected to an RBridge 35 and, on the other hand, the learning of the MAC address origin of the ARP-Path protocol, associating the mac origin of the frame with a port to create a tree of routes to the bridge which transmits the broadcast frame.

    Each bridge establishes the multiple paths in the manner described below to establish between the origin and destination bridges A and H. The origin bridge A sends a Path Request frame, in the format shown in Figure 17 with sequence identification number of path #i, type of disjoint path in links, and multicast destination address assigned to all AIl_Multiple_Disjoint_Paths_Bridges bridges, for all ports connected to other bridges. In each bridge, only the frame received first will be the only one retransmitted, 45 because duplicate frames subsequently received by other ports of the bridge during the blocking time are discarded when they are received by a port other than that associated with the MAC address of the frame. The frame is retransmitted by all ports except the arrival one. Each bridge crossed analyzes whether the Path Request frame is destined for it, in which case it will not be forwarded. Finally, only one Path Request #i frame (sequence number 50 of the first path) will be accepted at the destination border bridge H (frames received by other ports will be discarded by the bridge itself), which records the port through which it receives the frame and associates it with the directions of the two border bridges A and H as path #i (the sequence number of the first path) bidirectional to use. To confirm the
    establishment of the first bidirectional path between A and H, bridge H responds by sending a path confirmation path Path Confirm #i (the sequence number of the first path), with the format shown in Figure 17, through the port where the address of bridge H was received with origin address and destination address the address of bridge A. This frame travels in the opposite direction the path between A and H. Bridges D and F forward frame 5 through the port associated with the direction of A and the bidirectional path #i (the sequence number of the first path) between the bridges A and H and the two ports associated with said bidirectional path is recorded in its forwarding table thus leaving the bidirectional path #i (the sequence number of the first path) between A and H established, starting a validity timer for path #i. 10

    As shown in Figure 4, bridge A, once the disjoint path #i (the sequence number of the first path) is established, proceeds to establish a new disjoint path # i + 1 (the sequence number of the second path), starting the establishment timer for said path and sending a Path Request with sequence number identifier of 15 path # i + 1. Bridge A sends the request through all ports except for the port associated with path #i (the sequence number of the first path) to ensure that the new path # i + 1 uses different links than #i. Each bridge that receives the Path Request # i + 1 learns the source address of the A port and the source MAC address and associates it with the port through which it is first received, and forwards it through all other ports except for the ports associated with the path #i (the sequence number of the first path) (ports associated with the MAC address pair of the AB bridges). Finally, only one or no Path Request # i + 1 frame will be accepted (those received by other ports will be discarded by the bridge itself) on the H-border bridge, which will write down the port where it receives the frame and associate it with the addresses of the two border bridges A and H as bidirectional path # i + 1 to use. 25 To confirm the establishment of the bidirectional i + 1 path between A and H, bridge H responds by sending a path confirmation path Path Confirm # i + 1 through the port through which the address of bridge H was received, with origin address and destination address the address of bridge A. This frame travels in the opposite direction the path between A and H so that in each bridge of the network that receives this frame, the frame is forwarded by the associated port 30 to the direction of A and the bidirectional path # i + 1 between bridges A and H and the two ports associated with said bidirectional path is recorded in its forwarding table, thus leaving the bidirectional path # i + 1 between A and H established, starting the validity timer of the road.
    Figure 5 shows the establishment and confirmation of a third road disjoint in links 35 (# i + 2) between the border bridges and figure 6 the same for a fourth road (i + 3) disjoint in links. Frames are forwarded only by links that do not have a previously associated path.

    Figure 7 shows the four established paths, disjoint in links. 40

    Road erase

    When the Path Delete frame (A, H) is sent to the specific multicast address All_Multiple_Disjoint_Paths_Bridges from bridge A, that frame will cause the path that is indicated in the bridge tables crossed by the frame to be deleted.

    Figure 8 shows the erase of roads by means of a unicast package Path Delate #
    N. In Figure 8, the Path Delete # í + 2 frame has the origin of the bridge A and the destination of the bridge H, the protocol type Multiple_Disjoint_Path and the operation code 50 corresponding to Path Delete. It is sent through the port of A corresponding to the path # i + 2 that you want to eliminate and is forwarded in unicast for each bridge until you reach the destination bridge H.

    In each bridge crossed, the entrances corresponding to path # i + 2 between bridges A and H (tuple A-H-path # i + 2) are deleted.

    Figure 9 shows the remaining roads after deletion of path # i + 2.
     5
    Figure 10 shows the deletion of all roads between bridges A and H by means of a multicast All Path Delete frame, a frame that is sent by all ports associated with AH roads and has the origin of the bridge A and the destination address multicast All_Multiple_Disjoint_Paths_Bridges. In each crossed bridge, all the paths associated with the pair of nodes A-H are deleted and it is checked whether the internal destination address 10 dThe frame (H) corresponds to that of the bridge reached, in which case the frame is no longer forwarded. Otherwise, the frame is forwarded through all the ports of the bridge that are associated with roads between A and H.

    Figure 11 shows the remaining roads after the deletion of all roads between A and 15
    H.

    Successive establishment of disjoint paths in nodes

    Figure 12 shows the flow chart for the establishment of disjoint paths in 20 nodes. The path type indicator is at the disjoint value in nodes.

    Figure 13 shows the establishment of the first (#i) disjoint path in nodes, similar to the disjoint in links. Since it is the first path and there are no paths established in any node, the fastest path is selected and confirmed by H by means of a path confirmation Path Confirm #i.

    Figure 14 shows the establishment of path # i + 1 disjoint in nodes by means of the Path Request # i + 1 frame sent by all links except for the one that has confirmed path and forwarded by nodes that have no path assigned, discarded by nodes that have 30 assigned the path #i.

    Figure 15 shows the establishment of the path # i + 2 disjoint in nodes, sent to nodes K and G, but upon arriving before the frame forwarded by G, a bifurcated tree is created in G and whose fastest branch reaches H by The Ñ bridge, this road being the confirmed one, the 35 GIJH road expiring for not being confirmed.

    Figure 16 shows the failed attempt to establish the disjoint path on nodes # 1 + 3. It is sent in multicast. The Path Request # i + 3 frame, by the link that joins K by the only port not assigned to a road and reaches the bridge K. The bridge K does not have 40 exit ports without assigning to roads, so discards and does not forward it. When Path Request # i + 3 is not received on bridge H, its next path setting timer expires and the bridge terminates the path setting process. When path # i + 3 is not confirmed, it expires on each of the bridges crossed when the road setting timer expires. In the origin border bridge A, when no response is received in time to the Path Request of the path # i + 3, it expires and its entry is deleted.

    In each bridge, when a data frame arrives through a port, the terminal-border bridge table is consulted (figure 19, table 3), obtaining the addresses of the origin and destination border bridges to which they are connected. Performing the hash function, the 50 identifier of the path to be used is obtained, so by consulting in the routing table of the bridge with the MAC tuple origin MAC destination and sequence number path identifier, the output port of the bridge is obtained by the That route the plot.

    Bibliography

    [1] 802.1aq-2012-IEEE Standard for Local and metropolitan area networks-Media Access Control (MAC) Bridges and Virtual Bridged Local Area Networks-Amendment 20: Shortest Path Bridging. 5

    [2] D. B. Johnson. D. A. Maltz and J. Broch, "DSR The Dynamic Source Routing Protocol for Multi-hop Wireless Ad hoc Networks". in Ad hoc Networking, Chapter 5, C. E. Perkins. Eds. Addison Wesley, pp. 139-172, 2000.
     10
    [3] C. E. Perkins and E. M. Royer, "Ad hoc On-demand Distance Vector Routing", Proceedings of the 2nd Annual IEEE International Workshop on Mobile Computing Systems and Applications, pp. 90-100, February 1999.

    [4] S Lee and M. Gerla. "Split Multi-path Routing with Maximally Disjoint Paths in Ad Hoc 15 Networks", Proceedings of IEEE International Conference on Communications. Vol. 10, pp. 3201-3205, 2001.

    [5] M. K. Marina and S. R. Das. "On-demand Multi-path Distance Vector Routing in Ad Hoc Networks". Proceedings of the IEEE International Conference on Network Protocols. pp. 14-23, 20 Nov. 2001.

    [6] Z. Ye, S. V. Krishnamurthy and S. K. Tripathi, "A Framework for Reliable Routing in Mobile Ad Hoc Networks". Proceedings of the IEEE International Conference on Computer Communications. 2003. 25

    [7] V. Loscri and S. Marano, "A New Geographic Multi-path Protocol for Ad Hoc Networks to Reduce the Route Coupling Phenomenon", Proceedings of the 63rd IEEE Vehicular Technology Conference, VTC 2006-Spring, Vol. 3. pp . 1102-1106, 2006.
     30
    [8] M. Li, L. Zhang, V. O. K. Li, X. Shan and Y. Ren. "An Energy-Aware Multi-path Routing Protocol for Mobile Ad Hoc Networks", Proceedings of the ACM SIGCOMM Asia, April 2005.
    权利要求:
    Claims (8)
    [1]

    1. Iterative procedure for establishing multiple paths disjoint of data frames between any two border nodes of a network, comprising the following stages:
     5
    a) Terminal information. Each border bridge sends a multicast frame containing the bridge address and the list of the addresses of the terminals connected to the bridge;
    b) Road search stage, in which each bridge searches for the fastest route to each of the other bridges, by sending, through all active links of the bridge connected to other bridges, a multicast frame ;
    When received on a bridge, through a port with an assigned port identity, a frame comprising a source MAC address and a destination multicast address; fifteen
    1. Associate, then, in a table, for the purpose of forwarding backward from the bridge, the originating MAC address of the received frame to the identity of the port that first received the frame on said bridge, to an expiration indicator of said association and upon arrival of the frame and forward it through all the active ports of the bridge 20 except for the one received;

    [2]
    2. block this association from its creation, preventing the association of said origin address to another port of the bridge for a certain time;
     25

    [3]
    3. discard the multicast frames received by ports other than the one associated with the source address of the frame during the time that association is blocked;
    c) Road confirmation. Each recipient bridge of the search frame confirms the path selected in the network in step a), sending a unicast frame through the port through which the search frame was received;
    characterized by
     35
    d) In step a) of road search, the multicast road search frame generated by the origin bridge contains at least the MAC address of the destination bridge, the sequence identification number of the path to be established and the type of disjoint path ( disjoint in links nodes, disjoint in nodes) to establish;
     40
    e) in step a) indicated above, when the road search frame reaches a network bridge:
    - inspect the bridge the road type field:
     Four. Five
    - if the type of path is disjoint in links, forward the frame over all free ports (ports without any associated path identifier sequence number), but discard the frame if all ports have some associated path identifier sequence number;
    - If the type of path is disjoint in nodes and that bridge already has a number of 50 path identifier sequence associated with that pair of nodes, discard the frame. If, on the other hand, the bridge has no associated path, associate the path identifier, source MAC address and destination MAC address with the port
    by which the frame was first received, and forwarding said frame through the ports that are not associated with any path between said bridges;
    - If, as a result of the inspection of the type of road, the frame is to be forwarded by some port or the MAC address of the destination bridge contained within the frame 5 received is that of the bridge where it was received, create a new entry in the table , associating the MAC addresses of the origin bridge and the destination bridge of the frame to the port where it was first received, the sequence number of the road, the instant of time in which the frame arrived and a timer for the establishment (search and confirmation) of the road 10
    - Check if the MAC address of the destination bridge contained within the received frame is that of the bridge where it was received.
    If yes: 15
    - Confirm the establishment of the road by sending, through the port through which the road search multicast frame was received, a unicast frame confirming the establishment of the road with the originating address of the sending bridge, destination address of the originating bridge of the frame 20-way search and containing at least the sequence identifier number contained in the search frame, and an indicator of the type of path established (disjoint in links, disjoint in nodes);
    If not: 25
    - Forward the frame through all the ports of the bridge except for the one received.
    f) Upon receiving on a network bridge a unicast path confirmation frame, as described in step b) indicated above: 30
    - check the existence of a road request in the table with that identification sequence number pending confirmation.
    If yes: 35
    - confirm the association of the origin-MAC destination tuple to the first port where the road search frame was received, the road identifier sequence number and the port where the road confirmation frame was received; 40
    - Start the road expiration timer.
    If not: discard the path confirmation frame.
     Four. Five
    - check if the bridge receiving the road confirmation frame is the final recipient of the frame;
    If so,
    - deactivate the path setting timer that has been confirmed. fifty
    - discard the path confirmation frame.
    - Increase the number of path identifier sequence in a unit.
    - Repeat from step b) the road search procedure until the expiration of the road establishment timer due to lack of response from the destination bridge.
     5
    If not, forward the frame through the port associated with the road.

    [2]
    2. Frame forwarding method according to claim 1, characterized by
    When receiving a unicast frame in a network bridge whose protocol type field is not the 10 corresponding to Multiple Disjoint Path:
    - check if there is a path (associated output port) for that tuple of source and destination addresses in the routing tables;
     fifteen
    - if yes, perform a hash function (summary) of said tuple whose result is uniquely associated with a path and route the plot along the path resulting from said calculation, through the port associated with said tuple and the value of the identifying sequence number on the way;
     twenty
    - in all other cases: check if there is any bridge port associated with the destination MAC address of the frame.
    - if yes: forward the frame through that port;
     25
    - in other cases: discard the plot.

    [3]
    3. Method according to claims 1 and 2, characterized by
    - When the road setting timer expires on a bridge: 30
    - Delete provisional entry of the table associated with that road under construction;

    [4]
    4. Method according to claims 1 and 2, characterized by the additional erasure and forwarding steps,
    When a frame containing a Path Delete #N frame is received on a network bridge:
    - delete, from the table, for the purpose of forwarding, the association of the origin-MAC destination tuple and sequence identifier number of the road to the bridge ports, for roads 40 with that origin-MAC destination tuple MAC and number of path identifier sequence #N;
    - delete, from the table, for the purposes of forwarding, all associations of the origin-MAC destination tuple in the event that the contents of the path number field contain the value "all paths between origin and destination bridge" .
    - forward the frame through all ports, except for the one received.

    [5]
    5. Network bridge characterized by having the appropriate processing means for implementing the procedure of claims 1 to 4.

    [6]
    6. A switched telecommunications network characterized by comprising at least one network bridge defined according to claim 5.
    55
    类似技术:
    公开号 | 公开日 | 专利标题
    ES2540595B2|2016-02-02|PROCEDURE FOR ESTABLISHING AND DELETING ROADS AND FORWARDING SECTIONS FOR TRANSPORT CONNECTIONS AND NETWORK BRIDGES
    ES2361545B1|2012-05-08|PROCEDURE OF FURNITURE OF DATA SECTIONS AND NETWORK BRIDGE.
    ES2339782T3|2010-05-25|HYBRID PROTOCOL OF ROADING FOR A NETWORK WITH MESH TOPOLOGY.
    ES2262525T3|2006-12-01|TELECOMMUNICATIONS ROADING.
    Mittal et al.2009|Performance Comparison of AODV, DSR and ZRP Routing Protocols in MANET's
    ES2249280T3|2006-04-01|RUNNING IN A NETWORK OF SWITCHING PACKAGES WITH MOBILE TERMINALS.
    ES2243281T3|2005-12-01|TELECOMMUNICATIONS ROADING.
    ES2268165T3|2007-03-16|OPTIMATION OF LOCAL AGENT TO MANIPULATE MOBILE IP AND STATIC MPLS |.
    US20130094398A1|2013-04-18|Methods systems, and devices for robustness improvement in a mobile ad hoc network using reputation-based routing
    WO2020177580A1|2020-09-10|Method for processing data packets at node in bluetooth mesh network
    JP2014504045A|2014-02-13|COMMUNICATION SYSTEM, CONTROL DEVICE, COMMUNICATION METHOD, AND PROGRAM
    US20120224477A1|2012-09-06|Pruned forwarding set for scalable tunneling applications in distributed user plane
    JP2006279168A|2006-10-12|Communication apparatus for configuring adhoc network, bridge apparatus, and communication system
    US20170302563A1|2017-10-19|Content-centric network on-demand distance vector route method
    ES2638292B2|2018-04-17|Procedure for establishing and deleting multiple disjoint paths, frame forwarding and network bridge
    CN110831104A|2020-02-21|Routing method for linear topology wireless ad hoc network
    Mukherjee et al.2016|Low control overhead-based sleep scheduling in software-defined wireless sensor networks
    JP6921322B2|2021-08-18|Routing forwarding method for multi-host networks based on programmable network technology
    ES2647665B2|2018-04-24|Cooperative procedure, between bridges and controller, of repair of failed roads and network bridge
    ES2827842B2|2022-01-28|SEARCH PROCEDURE FOR MULTIPLE DISJOINT PATHS IN A STEP AND NETWORK NODE
    Mitelman et al.1999|Link state routing protocol with cluster based flooding for mobile ad-hoc computer networks
    Narongkhachavana et al.2017|Overhead reduction for route repair in mobile ad hoc networks
    WO2012152969A1|2012-11-15|Method for repairing data frame routes and network bridge
    Dharmaraj et al.2014|A rebroadcast technique for reducing routing overhead in mobile ad hoc network
    Nandakumar et al.2014|Traffic and energy aware routing in wireless ad hoc network
    同族专利:
    公开号 | 公开日
    WO2017158226A1|2017-09-21|
    ES2638292B2|2018-04-17|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    ES2540595B2|2013-12-10|2016-02-02|Universidad De Alcalá|PROCEDURE FOR ESTABLISHING AND DELETING ROADS AND FORWARDING SECTIONS FOR TRANSPORT CONNECTIONS AND NETWORK BRIDGES|ES2827842B2|2019-11-22|2022-01-28|Univ Alcala Henares|SEARCH PROCEDURE FOR MULTIPLE DISJOINT PATHS IN A STEP AND NETWORK NODE|
    法律状态:
    2018-04-17| FG2A| Definitive protection|Ref document number: 2638292 Country of ref document: ES Kind code of ref document: B2 Effective date: 20180417 |
    优先权:
    申请号 | 申请日 | 专利标题
    ES201600207A|ES2638292B2|2016-03-18|2016-03-18|Procedure for establishing and deleting multiple disjoint paths, frame forwarding and network bridge|ES201600207A| ES2638292B2|2016-03-18|2016-03-18|Procedure for establishing and deleting multiple disjoint paths, frame forwarding and network bridge|
    PCT/ES2017/070157| WO2017158226A1|2016-03-18|2017-03-17|Method for establishing and deleting multiple frame-forwarding disjoint paths, and network bridge|
    [返回顶部]